package queue;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 返回其中出现频率前 k 高的元素
 */
public class TopKElement {

    public static void main(String[] args) {
        int[] nums = new int[] {1,1,1,2,2,3};
        int k = 2;
        List<Integer> result = solve2(nums, k);
        System.out.println(result);
    }

    /**
     * 暴力法
     * @param nums
     * @param k
     * @return
     */
    private static List<Integer> solve(int[] nums, int k) {
        Map<Integer, Integer> hashMap = new HashMap<>(nums.length);
        for (int num : nums) {
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }
        return hashMap.entrySet().stream()
                .sorted((o1, o2) -> o2.getValue() - o1.getValue())
                .limit(k)
                .map(Map.Entry::getKey)
                .collect(Collectors.toList());
    }

    /**
     * 使用哈希表和优先级队列
     * @param nums
     * @param k
     * @return
     */
    private static List<Integer> solve2(int[] nums,int k) {
        Map<Integer, Integer> hashMap = new HashMap<>(nums.length);
        for (int num : nums) {
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }
        // 创建最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(hashMap::get));
        hashMap.keySet().forEach(num -> {
            minHeap.offer(num);
            // 队列大小大于k，最小值从队列中出队
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        });

        List<Integer> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll());
        }
        Collections.reverse(result);
        return result;
    }
}
